﻿//《寻找数组的中心下标》
//给你一个整数数组 nums ，请计算数组的 中心下标
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用
//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 - 1 

////思路
////1、用total记录数组全部元素的和，sum表示下标i左边区域元素的和
////2、依次遍历数组中的每个元素，如果total-sum-nums[i] == sum，则i就是中心下标，如果没有满足条件，则没有中心下标
//int pivotIndex(int* nums, int numsSize)
//{
//    int total = 0;
//    int sum = 0;
//    int i = 0;
//    for (i = 0; i < numsSize; i++) //先求total
//    {
//        total += nums[i];
//    }
//    for (i = 0; i < numsSize; i++)
//    {
//        if (total - sum - nums[i] == sum)
//        {
//            return i;
//        }
//        sum += nums[i];
//    }
//    return -1;
//}



//《多数元素》
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
//示例 1：
//输入：nums = [3, 2, 3]
//输出：3
//示例 2：
//输入：nums = [2, 2, 1, 1, 1, 2, 2]
//输出：2
//提示：
//n == nums.length
//1<=n<= 5 * 104
//-109<=nums[i] <= 109
////先排序，然后下标n/2就是多数元素，因为如果有多数元素，则一定大于n/2，也就是说多数元素至少占一半多
////快排
//// void myQsort(int* str, int left, int right)
//// {
////     if(left >= right)
////     {
////         return;
////     }
////     int l = left; //保存左区间下标
////     int r = right; //保存右区间下标
////     int term = str[left]; //让区间的第一个元素作为枢轴，此时第一个元素位置空缺
////     while(left < right)
////     {
////         while(left < right && str[right] >= term) //从右边查找小于枢轴的元素
////             right--;
////         str[left] = str[right]; //将找到的元素移动到左边left位置，此时right位置空缺
////         while(left < right && str[left] <= term) //从左边查找大于枢轴的元素
////             left++;
////         str[right] = str[left]; //将找到的元素移动到右边right位置，此时left位置空缺
////     }
////     str[left] = term; //将枢轴放到最终位置上
////     myQsort(str, l, left - 1); //对left左边区间排序
////     myQsort(str, left + 1, r); //对left右边区间排序
//// }
//
//int compare(const void* p1, const void* p2)
//{
//    return *(int*)p1 - *(int*)p2;
//}
//int majorityElement(int* nums, int numsSize)
//{
//    //myQsort(nums, 0, numsSize - 1);
//    qsort(nums, numsSize, sizeof(int), compare); //使用库函数
//    return nums[numsSize / 2];
//}


//《除自身以外数组的乘积》
//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//请不要使用除法，且在 O(n) 时间复杂度内完成此题
//示例 1:
//输入: nums = [1, 2, 3, 4]
//输出 : [24, 12, 8, 6]
//示例 2 :
//输入 : nums = [-1, 1, 0, -3, 3]
//输出 : [0, 0, 9, 0, 0]
//提示：
//2 <= nums.length <= 105
//- 30 <= nums[i] <= 30
//保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32位整数范围内(32是指bit位)
// 
//  //方法一：如果可以使用除法
//  //1、计算所有非0元素的乘积，记作result，并且统计所有非0元素的个数，记作zeroNum
//  //2、如果zeroNum == 0，则遍历一遍数组，每遍历到第i个元素的时候，就用result除以num[i]的结果赋值给answer[i]
//  //3、如果zeroNum == 1，非0元素nums[i]所对应的answer[i]为result，数组answer其它元素全为0
//  //4、如果zeroNum > 1，则数组answer所有元素为0
//  //时间复杂度O(n)
// int* productExceptSelf(int* nums, int numsSize, int* returnSize)
// {
//     int* answer = (int*)malloc(sizeof(int) * numsSize);
//     *returnSize = numsSize;
//     long long result = 1; //数组中非0元素的积
//     int zeroNum = 0; //统计数组中元素为0的个数
//     int i = 0;
//     for(i = 0; i < numsSize; i++)
//     {
//         if(nums[i] != 0)
//         {
//             result *= nums[i];
//         }
//         else
//         {
//             zeroNum++;
//         }
//     }
//     //printf("result = %d, zeroNum = %d\n", result, zeroNum);
//     if(zeroNum > 1)
//     {
//         for(i = 0; i < numsSize; i++)
//         {
//             answer[i] = 0;
//         }
//     }
//     else if(zeroNum == 1)
//     {
//         for(i = 0; i < numsSize; i++)
//         {
//             if(nums[i] != 0)
//             {
//                 answer[i] = 0;
//             }
//             else
//             {
//                 answer[i] = result;
//             }
//         }
//     }
//     else
//     {
//         for(i = 0; i < numsSize; i++)
//         {
//             answer[i] = result / nums[i];
//         }
//     }
//     return answer;
// }

//方法二：不能使用除法，直接暴力求解，时间复杂度是O(n^2)，怎样时间复杂度为O(n)，空间复杂度为O(1)
//采用左右乘积列表：计算answer[i]相当于计算nums[i]元素的前缀乘积和后缀乘积之积，所有先分别计算出每个元素的前缀乘积和后缀乘积，最后对应前缀乘积和后缀乘积相乘即可
//1、从前往后遍历每个元素，计算每个元素的前缀之积，存放在数组prefixProductArr中
//2、从后往前遍历每个元素，计算每个元素的后缀之积，存放在数组suffixProductArr中
//3、设置数组answer[i]就等于prefixProductArr[i] * suffixProductArr[i]
//分析：遍历了三遍数组，时间复杂度是O(n)，多开辟了存放前缀和后缀乘积的数组，空间复杂度是O(n)
// int* productExceptSelf(int* nums, int numsSize, int* returnSize)
// {
//     int* prefixProductArr = (int*)malloc(sizeof(int) * numsSize); //prefixProductArr[i]存放nums[i]的前缀乘积
//     int* suffixProductArr = (int*)malloc(sizeof(int) * numsSize); //suffixProductArr[i]存放nums[i]的后缀乘积
//     int* answer = (int*)malloc(sizeof(int) * numsSize); //存放返回值
//     *returnSize = numsSize;
//     int i = 0;
//     prefixProductArr[0] = 1; //第一个元素的前缀乘积是1
//     for(i = 1; i < numsSize; i++) //计算前缀乘积
//     {
//         prefixProductArr[i] = prefixProductArr[i - 1] * nums[i - 1]; //后面每个元素的前缀乘积是上一个元素的前缀乘积乘以上一个元素
//     }
//     suffixProductArr[numsSize - 1] = 1; //最后一个元素的后缀乘积是1
//     for(i = numsSize - 2; i >= 0; i--) //计算后缀乘积
//     {
//         suffixProductArr[i] = suffixProductArr[i + 1] * nums[i + 1]; //前面每个元素的后缀乘积是下一个元素的后缀乘积乘以下一个元素
//     }
//     for(i = 0; i < numsSize; i++) //设置数组answer
//     {
//         answer[i] = prefixProductArr[i] * suffixProductArr[i];
//     }
//     return answer;
// }
// //方法二改进
// //采用左右乘积列表--进阶：整体思路和上一种差不多，只不过不用开辟存放前缀乘积的数组，用answer数组充当，这样可以少开辟一个数组空间
// //1、从前往后遍历每个元素，计算每个元素的前缀之积，存放在数组answer中
// //2、从后往前遍历每个元素，计算每个元素的后缀之积，存放在数组suffixProductArr中
// //3、设置数组answer[i]就等于answer[i] * suffixProductArr[i]
// //分析：遍历了三遍数组，时间复杂度是O(n)，多开辟了存放后缀乘积的数组，空间复杂度是O(n)
// int* productExceptSelf(int* nums, int numsSize, int* returnSize)
// {
//     int* suffixProductArr = (int*)malloc(sizeof(int) * numsSize); //suffixProductArr[i]存放nums[i]的后缀乘积
//     int* answer = (int*)malloc(sizeof(int) * numsSize); //存放返回值和nums[i]的前缀乘积
//     *returnSize = numsSize;
//     int i = 0;
//     answer[0] = 1; //第一个元素的前缀乘积是1
//     for(i = 1; i < numsSize; i++) //计算前缀乘积
//     {
//         answer[i] = answer[i - 1] * nums[i - 1]; //后面每个元素的前缀乘积是上一个元素的前缀乘积乘以上一个元素
//     }
//     suffixProductArr[numsSize - 1] = 1; //最后一个元素的后缀乘积是1
//     for(i = numsSize - 2; i >= 0; i--) //计算后缀乘积
//     {
//         suffixProductArr[i] = suffixProductArr[i + 1] * nums[i + 1]; //前面每个元素的后缀乘积是下一个元素的后缀乘积乘以下一个元素
//     }
//     for(i = 0; i < numsSize; i++) //设置数组answer
//     {
//         answer[i] = answer[i] * suffixProductArr[i];
//     }
//     return answer;
// }

////方法二改进
////采用左右乘积列表--进阶：整体思路和上一种依然差不多，只不过也不用开辟存放后缀乘积的数组，对于上一种做法我们是将所有元素的后缀乘积计算出来之后再乘到answer数组上，其实我们可以每计算出来一个后缀乘积直接乘到answer上,为此开辟一个变量product，用来表示nums[i]的后缀乘积
////1、从前往后遍历每个元素，计算每个元素的前缀之积，存放在数组answer中
////2、从后往前遍历每个元素，计算每个元素的后缀之积，再乘到数组answer中
////分析：遍历了两遍数组，时间复杂度是O(n)，多开辟了一个变量，空间复杂度是O(1)
//int* productExceptSelf(int* nums, int numsSize, int* returnSize)
//{
//    int* answer = (int*)malloc(sizeof(int) * numsSize); //存放返回值和nums[i]的前缀乘积
//    *returnSize = numsSize;
//    int i = 0;
//    answer[0] = 1; //第一个元素的前缀乘积是1
//    for (i = 1; i < numsSize; i++) //计算前缀乘积
//    {
//        answer[i] = answer[i - 1] * nums[i - 1]; //后面每个元素的前缀乘积是上一个元素的前缀乘积乘以上一个元素
//    }
//    int product = 1; //表示元素的nums[i]的后缀乘积，初始化为1，也就是nums[numsSize-1]的后缀乘积
//    for (i = numsSize - 1; i >= 0; i--) //计算后缀乘积并乘到answer上
//    {
//        answer[i] = answer[i] * product;
//        product = product * nums[i]; //计算nums[i]的前一个元素的后缀乘积
//    }
//    return answer;
//}


////《不用加减乘除做加法》
////写一个函数，求两个整数之和，要求在函数体内不得使用 + 、 - 、 * 、 / 四则运算符号。
////数据范围：两个数都满足−10≤n≤1000
////进阶：空间复杂度O(1)，时间复杂度O(1)
////示例1
////输入：1, 2
////返回值：3
////示例2
////输入：0, 0
////返回值：0
//
// //思路：从二进制的角度看
// //1、a & b 查看两个数哪些二进制位都是1，都是1的二进制位就是要进位的位，如果结果为0表示没有进位，直接返回a | b就是a + b的结果，如果结果不为0表示有进位，然后再将结果左移一位，相当于进位，记作n1，然后进入第2步
// //2、a ^ b 查看两个数哪些二进制位只有一个1，这些都是非直接进位的位，可以直接写下来，记作n2
// //3、到这里并没有结束，因为进位有传递性，本来没有直接进位的位，可能会因为低位的进位也产生进位，所以将n1和n2分别赋值给a和b（随便分配）继续检查重复1，2两步，直到计算出结果
// //分析：进位多少次，就循环多少次，时间复杂度O(1),空间复杂度O(1)
//int Add(int a, int b)
//{
//    int n1 = 0;
//    int n2 = 0;
//    while (a & b) //循环进位
//    {
//        n1 = (a & b) << 1;
//        n2 = a ^ b;
//        a = n1;
//        b = n2;
//    }
//    return a | b;
//}


